from numpy import *

import randgraph

#
n = 200
rho = 0.6

adj_mat = randgraph.randgraph(n, rho)
adj_mat_new = zeros([n,n])


for i in range(n-1):
    adj_mat_new[i+1, 0:i+1] = adj_mat[0:i+1, i]
    adj_mat_new[0:i+1, i+1] = adj_mat[0:i+1, i]

print adj_mat
print adj_mat_new

nodes = [[i] for i in range(n)]
S = []
S_bar = nodes[:] 

S.extend([0])
S_bar.remove([0])

iter = 0
incumbent = 0.0


def find_weights(S_weights, target):
    weights = 0
    for elem in target:
        weights += S_weights[elem]
    return weights

def find_min_weights(S, S_bar, adj):
    # The following block of codes generates the new nodes given S and S_bar
    # The following codes needs to be refactored to deal with element of S_bar as a list of nodes
    S_weights = zeros(n)

    for node in S:
        S_weights += adj[node]

    conn_weights = zeros(len(S_bar))
    for i in range(len(S_bar)):
        conn_weights[i] = find_weights(S_weights, S_bar[i])

    max_weights = max( conn_weights )
    max_weights_ind = argmax( conn_weights )
    new_node = S_bar[max_weights_ind]
    
    """
    # Old codes
    max_weights = max( sum_weights_vec[S_bar] )
    # find the node to add to S
    for node in S_bar:
        if sum_weights_vec[node] == max_weights:
            new_node = node
            break
    """
    return new_node, max_weights

#Outter while loop
while len(nodes) > 2:
    S = []
    S_bar = list(nodes)
    S.extend([0])
    S_bar.remove([0])
    iter = 0

    #Inner while loop
    while len(S_bar) > 1:
        iter += 1
        new_node, maxweights = find_min_weights(S, S_bar, adj_mat_new)
        S.extend( new_node )
        S_bar.remove( new_node )
        """
        print "Step ", iter
        print S
        print S_bar
        """
        
    p = new_node
    q = S_bar[0]

    new_node, max_weights = find_min_weights(S, S_bar, adj_mat_new)

    incumbent = max(max_weights, incumbent)

    # Then merge the last two nodes 
    nodes.remove(p)
    nodes.remove(q)
    nodes.append( p+q )


# Only two nodes left
new_node, max_weights = find_min_weights(S, S_bar, adj_mat_new)
incumbent = max(max_weights, incumbent)

print incumbent

#update S and S_bar

"""
S = []
S_bar = list(nodes)
S.append(0)
S_bar.remove(0)
"""
    
